/*
练习1-1 二分查找
分数 20
作者 陈越
单位 浙江大学

查找算法中的“二分法”是这样定义的：给定 n 个从小到大排好序的整数序列
data，以及某待查找整数 x，我们的目标是找到 x 在 data 中的位置。
具体来说，不妨假设整数序列存储为一个序列
array，这个序列的结构定义在下面给出，数据存放在数组 data 中。若有 array->data[i]
= x，则返回 i；否则返回失败标记 NotFound 表示没有找到。注意 C 语言数组下标从 0
开始。 二分法是先找到序列的中点 array->data[middle]，与 x 进行比较，若
array->data[middle] > x，则在左边的子序列中查找 x；若 array->data[middle] <
x，则在右边的子序列中查找 x; 否则两者相等，则返回中点下标
middle。试用一个函数实现二分查找的功能，并分析最坏、最好情况下的时间、空间复杂度。
函数接口定义：

Position BinarySearch( ArrPtr array, ElemSet x );

其中ArrPtr结构定义如下：

typedef int Position;  // 整型下标，表示元素的位置

typedef struct ArrNode *ArrPtr;

struct ArrNode {
    ElemSet *data; // 存储数据的数组；ElemSet是用户定义的数据类型
    int size;      // 数组的大小
};

函数接口定义中，ElemSet 是用户定义的数据类型，例如 int、double 或者 char
等，要求可以通过 >、==、< 进行比较，并且题目保证传入的数据是递增有序的。
*/

#include <stdio.h>
#include <stdlib.h>

#define kMaxSize 10
#define NotFound -1

typedef int ElemSet;
typedef int Position; /* 整型下标，表示元素的位置 */
typedef struct ArrNode *ArrPtr;
struct ArrNode {
    ElemSet *data; /* 存储数据的数组；ElemSet是用户定义的数据类型 */
    int size;      /* 数组的大小 */
};

Position BinarySearch(ArrPtr array, ElemSet x);

int main(void) {
    int i, n;
    ArrPtr array;
    ElemSet x;

    array = (ArrPtr)malloc(sizeof(struct ArrNode));
    scanf("%d", &n);
    array->size = n;
    array->data = (int *)malloc(sizeof(int) * array->size);
    for (i = 0; i < n; i++) {
        scanf("%d", &array->data[i]);
    }
    scanf("%d", &x);
    printf("%d\n", BinarySearch(array, x));
    return 0;
}
/* 你的代码将被嵌在这里 */

Position _BinarySearch(ArrPtr array, ElemSet x, int start, int end) {
    if (start > end) {
        return NotFound;
    }
    int mid = (start + end) / 2;
    if (array->data[mid] == x) {
        return mid;
    } else if (array->data[mid] > x) {
        return _BinarySearch(array, x, start, mid - 1);
    } else {
        return _BinarySearch(array, x, mid + 1, end);
    }
}

Position BinarySearch(ArrPtr array, ElemSet x) {
    return _BinarySearch(array, x, 0, array->size - 1);
}